#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int maxv = 1003;

int c[maxv];
int v[maxv];
int vis[maxv][maxv];

int T,n;

int f(int i, int t) //用t时间去完成前i个项目
{
    if(vis[i][t])
        return vis[i][t];
    if(i == 0)
        return 0;
    if(t-c[i]<0)
        return vis[i][t] = f(i-1,t);
    return vis[i][t] = max(f(i-1,t-c[i])+v[i],f(i-1,t));
}

int main()
{
    memset(vis,0,sizeof(vis));
    cin>>T>>n;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",c+i);
        scanf("%d",v+i);
        

    }
    printf("%d", f(n,T));

    return 0;


}
